package study.算法Algorithm.排序算法.插入排序;

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
//        m01();
//        m02();
        m03();
    }

    private static void m03() {
        int arr[] = {101, 34, 110, 1};
        for (int i = 0; i < arr.length - 1; i++) {
            int insertVal = arr[i + 1];
            int insertIndex = i;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex+1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertVal != arr[insertIndex + 1]) {
                arr[insertIndex + 1] = insertVal;
                System.out.println("第" + (i + 1) + "趟排序");
                System.out.println(Arrays.toString(arr));
            }
        }
    }

    private static void m02() {
        int arr[] = {101, 34, 110, 1};
        for (int i = 0; i < arr.length - 1; i++) {
            int insertVal = arr[i + 1];
            int insertIndex = i;
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            if (insertVal != arr[insertIndex + 1]) {
                arr[insertIndex + 1] = insertVal;
                System.out.println("第" + (i + 1) + "趟排序");
                System.out.println(Arrays.toString(arr));
            }
        }
    }

    private static void m01() {
        int arr[] = {101, 34, 110, 1};
        for (int i = 0; i < arr.length - 1; i++) {
            int insertVal = arr[i + 1];
            int insertIndex = i;
            //给insertVal找到插入的位置   insertIndex>=0这段  保证不数组越界
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                //说明待插入数还没找到插入到谁后面
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //当退出while循环时，说明插入的位置找到，
            //判断是否需要赋值
            if (insertVal != arr[insertIndex + 1]) {
                arr[insertIndex + 1] = insertVal;
                System.out.println("第" + (i + 1) + "趟排序");
                System.out.println(Arrays.toString(arr));
            }
        }
    }
}
